/**
 * 给定两个二叉树，编写一个函数来检验它们是否相同。
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 */

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}
// 递归校验
var isSameTree = function (p,q) {
    //p,q同步向下
    if(p === null && q === null) return true
    if(p === null || q === null) return false
    // 递归子树校验，若节点值不等直接短路false
    return (p.val === q.val) && (isSameTree(p.left, q.left)) && (isSameTree(p.right, q.right))
}
// bfs广搜迭代校验：层序遍历
var isSameTreeByBFS = function (p,q) {
    const queue = []
    queue.push({p,q})
    while(queue.length !== 0) {
        let cur = queue.shift()
        if(cur.p === null && cur.q === null) continue
        if(cur.p === null || cur.q === null) return false
        if(cur.p.val !== cur.q.val) return false
        queue.push({p: cur.p.left,q: cur.q.left})
        queue.push({p: cur.p.right,q: cur.q.right})
    }
    return true
}
